#include <iostream>
#include<vector>
using namespace std;

// 定义顺序表类 SeqList，存放 int 类型数据
class SeqList {
    private:
        int* data;       // 数组指针，用于存放顺序表中的元素
        int maxSize;     // 顺序表的最大容量
        int length;      // 当前顺序表中的元素个数
    public:
        // 构造函数，初始化顺序表
        SeqList(int size):maxSize(size) {
            data = new int[maxSize]; // 动态分配内存空间
            length = 0;              // 初始长度为 0
        }
        
        // 析构函数，释放动态分配的内存
        ~SeqList() {
            delete[] data;
        }

        // 重载[]运算符，提供访问数组元素的方式
        int& operator[](int index) {
            return data[index];  
        }

        // 打印顺序表的内容
        void printList(){
            for(int i=0; i<length; i++){
                cout<<data[i]<<", ";  // 输出每个元素
            }
            cout<<endl;
        }

        // 插入元素到顺序表中，默认插入到表末尾
        bool insert(int element, int index=-1){
            if(index == -1) {  // 如果未提供插入位置，默认插入到末尾
                index = length;
            }
            if(length >= maxSize) {  // 检查表是否已满
                cout << "顺序存储结构满了\n";
                return false; 
            }
            if(index < -1 || index >= maxSize) {  // 检查插入位置是否合法
                cout << "不能在" << index << "位置插入\n";
                return false;
            }
            // 将 index 及之后的元素向后移动
            for(int i = length; i > index; i--){
                data[i] = data[i-1];
            }
            data[index] = element;  // 在指定位置插入新元素
            ++length;
            return true;
        }

        // 删除指定位置的元素，默认删除最后一个
        bool remove(int index = -1){
            if(index < 0 || index >= length) {
                cout << "index输入有误";
                return false;
            }
            // 将 index 后面的元素依次向前移动
            for(int i = index; i < length - 1; i++) {
                data[i] = data[i+1];
            }
            --length;  // 减少表长度
            return true;
        }

        // 获取顺序表当前长度
        int len() const {
            return length;
        }

        // (1) 删除给定元素的算法
        bool remove_ele(int element) {
            int mylist[length];  // 存储找到的目标元素的索引
            int k = -1;
            // 遍历顺序表，查找指定元素
            for (int i = 0; i < length; ++i) {
                if (data[i] == element) {
                    k++;
                    mylist[k] = i;  // 记录每次找到的索引
                }
            }
            // 如果没有找到，返回false
            if (k == -1) {
                cout << "没有找到该元素\n";
                return false;
            }
            // 逐个删除找到的元素
            while(k >= 0){
                remove(mylist[k]);
                k--;
            }
            return true;
        }

        // (2) 对于已排好序的线性表，删除所有重复元素的算法
        bool remove_duplicates() {
            if (length < 2) return true; // 长度小于2，无需去重
            int j = 0;  // j 用于记录去重后的索引
            for (int i = 1; i < length; ++i) {
                if (data[i] != data[j]) {
                    j++;
                    data[j] = data[i];  // 将非重复元素移到前面
                }
            }
            length = j + 1;  // 更新去重后的长度
            return true;
        }

        // (3) 线性表“逆置”算法
        void reverse() {
            for (int i = 0; i < length / 2; ++i) {
                int temp = data[i];  // 交换前后元素
                data[i] = data[length - 1 - i];
                data[length - 1 - i] = temp;
            }
        }

        // 逆置顺序表的某个区间，用于循环移动操作
        void reverse_segment(int start, int end) {
            while (start < end) {
                int temp = data[start];
                data[start] = data[end];
                data[end] = temp;
                ++start;
                --end;
            }
        }

        // (4) 线性表循环左移 k 位的算法
        void left_rotate(int k) {
            k = k % length;  // 防止 k 大于 length
            reverse_segment(0, k - 1);       // 逆置前 k 个元素
            reverse_segment(k, length - 1);  // 逆置后 length-k 个元素
            reverse();                       // 逆置整个数组
        }

        // (4) 线性表循环右移 k 位的算法
        void right_rotate(int k) {
            left_rotate(length - k);  // 循环右移 k 位等价于左移 length - k 位
        }

        // (5) 合并两个已排好序的线性表的算法
        SeqList merge(const SeqList& other) {
            SeqList result(maxSize + other.maxSize);  // 新表容量为两个表之和
            int i = 0, j = 0, k = 0;

            // 合并两个有序表
            while (i < length && j < other.length) {
                if (data[i] < other.data[j]) {
                    result.data[k++] = data[i++];
                } 
                else {
                    result.data[k++] = other.data[j++];
                }
            }

            // 处理剩余元素
            while (i < length) {
                result.data[k++] = data[i++];
            }
            while (j < other.length) {
                result.data[k++] = other.data[j++];
            }

            result.length = k;  // 更新结果表的长度
            return result;
        }
};


int main(){
    // 创建一个大小为20的顺序表 a
    SeqList a(20);
    a.insert(1);
    a.insert(1);
    a.insert(2);
    a.insert(2);
    a.insert(3);
    a.insert(4);
    a.insert(4);
    cout<<"最开始的数组: ";
    a.printList();
    
    // (1) 删除指定元素1
    a.remove_ele(1);
    cout<<"(1)删除1之后: ";
    a.printList();

    // (2) 删除顺序表中的所有重复元素
    a.remove_duplicates();
    cout<<"(2)对于已排好序的线性表，删除所有重复元素的算法:";
    a.printList();

    // (3) 逆置顺序表
    a.reverse();
    cout<<"(3) 线性表“逆置”算法：";
    a.printList();

    // (4) 循环左移1位
    a.left_rotate(1);
    cout<<"(4) 线性表循环左移 1 位的算法: ";
    a.printList();

    // (4) 循环右移1位
    a.right_rotate(1);
    cout<<"(4) 线性表循环右移 1 位的算法: ";
    a.printList();

    // (5) 合并两个已排好序的线性表
    cout<<"(5) 合并两个已排好序的线性表的算法："<<endl;
    SeqList b(20);  // 创建第一个表 b
    SeqList c(20);  // 创建第二个表 c
    b.insert(0);
    b.insert(2);
    b.insert(4);
    c.insert(1);
    c.insert(3);
    c.insert(5);
    cout<<"第一个: ";
    b.printList();
    cout<<"第二个: ";
    c.printList();
    cout<<"合并后: ";
    b.merge(c).printList();  // 合并表 b 和表 c 并打印结果
    return 0;
}

